Drilling [A]

Memory limit: 128 MB

Byteman is the person in charge of a team that is looking for crude oil reservoirs. He has made two boreholes: he found crude oil in point and found out that there is no crude oil in point . It is known that the oil reservoir occupies a connected fragment of segment with one end at point . Now Byteman has to check, how far, along the segment connecting points and , does the oil reservoir reach. It is not that simple, however, because in some locations one can drill faster than in other locations. Moreover, Byteman's team is rather small, so they can drill in at most one location at a time. Byteman's boss would like him to predetermine when he will be able to identify the boundary of the oil reservoir.

Byteman has asked you for help. He has divided the segment connecting points and into segments of equal length. If we assume that point has coordinate 0, and point coordinate , then there are points with coordinates between them. It is enough to find the farthest from of these points in which some crude oil occurs. Byteman has informed you about the amounts of time necessary for making boreholes in these points - they are equal to respectively. You should create such a plan of drilling, that the time necessary to identify the oil reservoir's boundary is shortest possible, assuming the worst-case scenario.

Input

The first line of the standard input contains a single positive integer (). The second line contains positive integers separated by single spaces ().

Output

Your program should write a single integer to the standard output - the smallest amount of time that Byteman has to spend (assuming the worst-case scenario) drilling in search of oil, to be sure that he will identify the reservoir's boundary.

Example

For the input data:

4
8 24 12 6

the correct result is:

42

Explanation of the example. Assume that Byteman makes the first borehole at point , what takes him time . It can then turn out that he finds crude oil there and he will have to check, how far to the right does the reservoir reach. He will need two more boreholes, making which requires units of time in the worst case. Therefore, in this case Byteman will spend in total units of time drilling.

It turns out that it is better to start at point . If there is no crude oil there, it is sufficient to check point . However, in the worst case Byteman will have to make two more boreholes in points and and end his work in total time equal to .

Task author: Marcin Kubica.